#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-12-14 10:43 上午
# @Author  : yangdy
# @File    : 剑指 Offer 42. 连续子数组的最大和
# @Software: PyCharmCE
from tools.my_methods import *


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if all(x < 0 for x in nums):
            return max(nums)
        # dp = [nums[0] if nums[0] >= 0 else 0]
        # for x in nums[1:]:
        dp = [0]
        for x in nums:
            if x + dp[-1] >= 0:
                dp.append(x + dp[-1])
            else:
                dp.append(x if x >= 0 else 0)
        return max(dp)


questions = [
    ([-2, 1, -3, 4, -1, 2, 1, -5, 4],),
]

work(questions, lambda q: Solution().maxSubArray(q[0]))
